1. Tree Recursion
1. 1.1. Order of Recursive Calls
  1. 1.1.1. e.g.1:Cascade
  2. 1.1.2. e.g.2:Inverse Cascade
2. 1.2. Tree Recursion
  1. 1.2.1. e.g.1 斐波那契数列
  2. 1.2.2. e.g.2 计算分区

Tree Recursion

Order of Recursive Calls

e.g.1:Cascade

def cascade(n):
    if n<10:
        print(n)
    else:
        print(n)
        cascade(n//10)
        print(n)

结果为

>>> cascade(12345)
12345
1234
123
12
1
12
123
1234
12345

首先一直调用cascade到底，返回None，从调用入口出来后继续执行cascade下面的语句

还可以缩短为以下

def cascade_short(n):
    print(n)
    if n>10:
        cascade(n//10)
        print(n)

e.g.2:Inverse Cascade

def inverse_cascade(n):
    grow(n)
    print(n)
    shrink(n)
    
def f_then_g(f,g,n):
    if n:
        f(n)
        g(n)

grow = lambda n: f_then_g(grow,print,n//10)
shrink = lambda n: f_then_g(print,shrink,n//10)

grow先进行处理，每次将数字缩短一节，到达递归底部后退出时便是从小到大依次输出

shrink先打印出来当前n，然后将数字缩短一节，这样递归过程便实现了从大到小依次输出

Tree Recursion

当递归函数对自身调用超过一次时，发生树形递归，产生树状过程

e.g.1 斐波那契数列

def fib(n):
    if n==0:
        return 0
    elif n==1:
        return 1
    else:
        return fib(n-1)+fib(n-2)

e.g.2 计算分区

将正整数n分为大小不超过m的分区的方式有多少种，即n能以多少种方式表示为递增的不超过m部分之和

e.g. count_partitions(6,4)

有以下可能：

……

分为两种情况考虑：

至少分一个4
不分4

这样我们可以把递归问题拆分为两个小问题，将两种情况相加

count_partitions(2,4)
count_partitions(6,3)

以此类推，count_partitions(6,3)按同样方式考虑，分3与不分3，直到递归底部

def count_partitions(n,m):
    if n==0:
        return 1
    elif n<0:
        return 0
    elif m==0:
        return 0
    else:
        with_m = count_partitions(n-m,m)
        without_m = count_partitions(n,m-1)
        return with_m+without_m

本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可

红魔咖啡馆

【CS61A】CS61A——Tree Recursion

Tree Recursion

Order of Recursive Calls

e.g.1:Cascade

e.g.2:Inverse Cascade

Tree Recursion

e.g.1 斐波那契数列

e.g.2 计算分区